package com.dh.offer;

import org.junit.Assert;
import org.junit.Test;

/**
 * @ClassName: _53_que_shi_de_shu_zi_lcof
 * @Description: 剑指 Offer 53 - II. 0～n-1中缺失的数字
 * <p>
 * https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/
 * @Author: shouzimu
 * @Date: 2020/12/1 11:52
 */
public class _53_que_shi_de_shu_zi_lcof {
    public int missingNumber(int[] nums) {
        if (nums[0] != 0) {
            return 0;
        }

        //二分
        int left = 0;
        int right = nums.length;
        int mid = 0;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (mid >= nums.length) {
                break;
            }
            //find right
            if (nums[mid] == mid) {
                left = mid + 1;
            } else {
                // mid < nums[mid] 左边缺了
                if (mid < nums[mid]) {
                    right = mid - 1;
                    //缺的是当前
                    if (mid > 0 && nums[mid - 1] == mid - 1) {
                        return mid;
                    }
                }
            }
        }
        return mid;
    }

    @Test
    public void missingNumberTest() {
        Assert.assertEquals(34, missingNumber(new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49}));
        Assert.assertEquals(9, missingNumber(new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8}));
        Assert.assertEquals(8, missingNumber(new int[]{0, 1, 2, 3, 4, 5, 6, 7, 9}));
        Assert.assertEquals(4, missingNumber(new int[]{0, 1, 2, 3, 5, 6, 7, 8, 9}));
        Assert.assertEquals(0, missingNumber(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}));
        Assert.assertEquals(3, missingNumber(new int[]{0, 1, 2}));
        Assert.assertEquals(2, missingNumber(new int[]{0, 1, 3}));
        Assert.assertEquals(1, missingNumber(new int[]{0}));
    }
}
